public class RealLinkedList {
    public ListNode head;    //头节点
    public ListNode tail;   //指向链表的最后一个结点，有了tail以后，尾插法的时间复杂度变成O（1）
    public void addFirst(int data){ //头插法
        ListNode node = new ListNode(data);
        if (this.head == null){
            this.head = node;
            this.tail = node;    //头插法的话，tail始终是最开始那个head，所以只需要赋值一次
        }else{
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
        System.out.println( data+" 元素头部插入成功");
    }
    public void addLast(int data){ //尾插法
        ListNode node = new ListNode(data);
        if (this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        System.out.println(data+" 元素尾部插入成功");
    }
    public boolean addIndex(int index,int data){  //位置插入
        if (index < 0 || index > this.size()){
            return false;
        }
        if (index == 0){
            this.addFirst(data);
            return true;
        }
        if (index == this.size()){
            this.addLast(data);
            return true;
        }

        ListNode node = new ListNode(data);
        ListNode cur = searchIndex(index);

        node.prev = cur.prev;
        node.next = cur;
        cur.prev.next = node;
        cur.prev = node;
        System.out.println(index+" 位置成功插入元素 "+data);
        return true;
    }
    public ListNode searchIndex(int index){//遍历寻找指定位置元素
        ListNode cur = this.head;
        int i = 0;
        while (i < index){
            cur = cur.next;
            i++;
        }
        return cur;
    }
    public boolean contains(int key){//查找链表中有没有指定元素
        if (this.head == null){
            System.out.println("链表为空");
            return false;
        }
        ListNode p = this.head;
        while(p != null){
            if(p.data == key){
                System.out.println(key+" 存在于链表中");
                return true;
            }
            p = p.next;
        }
        System.out.println(key+" 未找到");
        return false;
    }
    public int size(){//链表大小
        ListNode p = this.head;
        int len = 0;
        while (p != null){
            p = p.next;
            len++;
        }

        return len;
    }
    public void display(){  //打印链表内容
        ListNode cur = head;
        while (cur != null){
            System.out.println(cur.data);
            cur = cur.next;
        }
        System.out.println("链表打印成功");
    }
    public void remove(int key){  //删除指定元素
        if (this.head == null){
            System.out.println("链表为空");
            return ;
        }
        if (this.head.data == key){    //如果要删除的是第一个结点，进行特判
            this.head = head.next;
            this.head.prev = null;
            //注意这里要把prev置空，在单向链表中不需要置空
            // 是因为单链表head=head.next后，已经没有引用是第一个结点的了，堆中的空间会被自动回收，而这里的还有prev引用着第一个结点，固需要置空
            System.out.println(key+" 删除成功");
            return;
        }
        ListNode cur = this.head;
        while (cur != null){
            if (cur.data == key){
                cur.prev.next = cur.next;
                if (cur.next == null){
                    this.tail = cur.prev;    //如果删除的是最后一个结点，不要忘记对tail的值进行修改
                    break;
                }
                cur.next.prev = cur.prev;    //如果cur为最后一个结点，这里会出现空指针异常
                break;
            }
            cur = cur.next;
        }
        System.out.println(key+" 删除成功");
    }
}
